НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №1
з навчальної дисципліни “Програмування складних алгоритмів”
Тема:
СКЛАДНІСТЬ АЛГОРИТМУ
Варіант №12
Київ 2022
Мета:
Метою лабораторної роботи є отримання практичних навичок визначати часову складність алгоритму. Навчитися будувати алгоритми з мінімальною часовою складністю для вирішення поставлених задач.
Теоретична частина
Алгоритм – це скінченна послідовність команд, які треба виконати над вхідними даними для отримання результату.
Основними мірами обчислювальною складності алгоритмів є:
– часова складність, яка характеризує час, необхідний для виконання алгоритму на даній машині; цей час, як правило, визначається кількістю операцій, які потрібно виконати для реалізації алгоритму;
– ємнісна складність, яка характеризує пам’ять, необхідну для виконання алгоритму.
Часова та ємнісна складність тісно пов’язані між собою. Обидві є функціями від розміру вхідних даних.
Складність алгоритму описуватиметься функцією f(n), де n – розмір вхідних даних. Важливе теоретичне і практичне значення має класифікація алгоритмів, яка бере до увагу швидкість зростання цієї функції.
Найпоширеніші функції, які зустрічаються в аналізі алгоритмів, а саме:
O(1) – константа;
O(log n) – логарифмічне;
O(n) – лінійне;
O(n · log n) – лінеарітмічне;
O(n²) – квадратичне;
O(2ⁿ) – експоненціальне;
O(n!) – факторіальне;
де n → ∞.
O(1)
Незалежно від того, що ви згодовуєте алгоритму, він все одно працюватиме за той самий проміжок часу.
O(log n)
Час роботи алгоритму ледь збільшився при збільшенні вхідних даних.
O(n)
Час розрахунку збільшується з тією ж швидкістю, що і вхідні дані.
O(n²)
Час розрахунку збільшується зі швидкістю n².
O(n!)
Час роботи збільшується з темпами n!, тобто, якщо n дорівнює 5, це 5x4x3x2x1 або 120. Це не так вже й погано при малих значеннях n, але при великих значеннях алгоритм стає нереально обрахувати.
Розрахунок часової складності
Алгоритм 1
Розмір
Складність
Кількість ітерацій
Час виконання
10х10
O(n^2)
Квадратична складність
2862
16 нс
50х50
2189182
21 нс
34173682
27 нс
100х100
20937666752
711 нс
500х500
Алгоритм 2
Розмір
Складність
Кількість ітерацій
Час виконання
10х10
O(n^2)
Квадратична складність
3254
8 нс
50х50
6324174
27 нс
100х100
102581844
21 нс
500х500
81045860984
165 нс
Завдання:
Використовуючи алгоритми, згідно варіанту завдання, скласти програму розрахунку заданих величин та провести аналіз ефективності реалізованих алгоритмів.
Сформувати двовимірний масив цілих чисел, використовуючи датчик випадкових чисел. Використати оголошення масиву на n елементів (кількість елементів задавати з екрану). Провести оцінку часової складності алгоритму, використовуючи О-символіку в найгіршому або/і в середньому. Порівняти час роботи та кількість ітерацій/кількість к р о к і в р о б о т и п р о г р а м и з р із н о ю розмірністю масиву (10x10, 50x50, 100x100, 500x500). Оцінку часу роботи навести у вигляді графіка, або таблиці.
Використовуючи алгоритми, згідно варіанту завдання, скласти програму розрахунку заданих величин та провести аналіз ефективності реалізованих алгоритмів.
Завдання до Варіанту_12
Знайти стовпчик з найбільшою послідовністю елементів, впорядкованих за зростанням.
Провести обмін елементів матриці за вказаною схемою
Результати виконання лабораторної роботи:
Код:
//Лабораторна робота №1_ПСА
//ТР-15_Ткаченко_Майя, Варіант_12
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
void create_array(int n, int array[n][n]);
void display_array(int n, int array[n][n]);
void task1(int n, int array[n][n]);
void task2(int n, int array[n][n]);
int main(void)
{
printf("\n-----------------------------------------\n");
printf("<<<~~~ Завдання 1: Знайти стовпчик з найбільшою послідовністю елементів, впорядкованих за зростанням.\n");
printf("--------...
